/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Home-pc
 * Date: 2023-09-01
 * Time: 11:05
 */
public class HashBucket {
    static class Node{
        private int key;
        private int val;
        private  Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;
    public int usedSize;
    private static final float DEFAULT_LOAD_FACTOR=0.75f;//默认负载因子为0.75

    public HashBucket() {
        this.array = new Node[10];
    }

    //put
    public void put(int key,int val){
        Node node=new Node(key,val);//新建一个节点
        int index=key%array.length;//确认在数组中的位置
        Node cur=array[index];//数组在该位置的首个节点，也是链表的头节点
        while(cur!=null){//遍历这个链表
            if(cur.key==key){//如果找到了这个key值，那么需要改变它的val值
                cur.val=val;
                return;
            }
            cur=cur.next;
        }
        //走到这里说明该位置没有那个key，我们使用头插放入该节点
        node.next=array[index];//先链接后面的节点
        array[index]=node;//变动头节点
        
        usedSize++;
        //判断负载因子，超过负载因子，需要进行扩容
        if(loadFactor()>=DEFAULT_LOAD_FACTOR){
            resize();
        }
    }

    private void resize() {
        Node[] tmpArray=new Node[array.length*2];
        for (int i = 0; i <array.length; i++) {//遍历原来的数组，将原来数组中的元素重新放置位置
            Node cur=array[i];
            while(cur!=null){
                Node curNext=cur.next;//记录当前链表节点的下一个位置，为遍历节点做准备
                int index=cur.key%tmpArray.length;//为当前下标的节点重新确认在新数组的位置
                cur.next=tmpArray[index];//头插新数组中的位置
                tmpArray[index]=cur;
                cur=curNext;
            }
        }
        array=tmpArray;
    }

    private float loadFactor(){
        return usedSize*1.0f/array.length;
    }

    //取数据 get
    public  int get(int key){
        int index=key%array.length;
        Node cur=array[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.val;
            }
            cur=cur.next;
        }
        return -1;
    }
    
}
